Add a Rate Limit to Your Website

Suppose you have a ressource on the web (for example an API) that either generates a lot of load, or that is prone to be abused by excessive use, you want to rate-limit it. That is, only a certain number of requests is allowed per time-period.

A possible way to do this is to use Memcache to record the number of requests received per a certain time period.

Task: Only allow 1000 requests per 5 minutes

First attempt:
The naive approach would be to have a key rate-limit-1.2.3.4 (where 1.2.3.4 would be the client’s IP address) with a expiration time of 5 minutes (aka 300 seconds) and increment it with every request. But consider this:

10:00: 250 reqs -> value 250
10:02: 500 reqs -> value 750
10:04: 250 reqs -> value 1000
10:06: 100 reqs -> value 1250 -> fails! (though there were only 850 requests in the last 5 minutes)

Whats the problem?

Memcache renews the expiration time with every set.

Second attempt:
Have a new key every 5 minutes: rate-limit-1.2.3.4-${minutes modulo 5}. This circumvents the problem that the key expiration but creates another one:

10:00: 250 reqs -> value 250
10:02: 500 reqs -> value 750
10:04: 250 reqs -> value 1000
10:06: 300 reqs -> value 300 -> doesn’t fail! (though there were 1050 requests in the last 5 minutes)

Solution:
Store the value for each minute separately: rate-limit-1.2.3.4-$hour$minute. When checking, query all the keys in the last 5 minutes to calculate the requests in the last 5 minutes.

Sample code:


foreach ($this->getKeys($minutes) as $key) {
    $requests += $this->memcache->get($key);
}

$this->memcache->increment($key, 1);

if ($requests > $allowedRequests) throw new RateExceededException;

For your convenience I have open sourced my code at github: php-ratelimiter.

Leave a Reply

Only people in my network can comment.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

To respond on your own website, enter the URL of your response which should contain a link to this post's permalink URL. Your response will then appear (possibly after moderation) on this page. Want to update or remove your response? Update or delete your post and re-enter your post's URL again. (Find out more about Webmentions.)